package com.zjw.algorithm.ready1;

import com.zjw.algorithm.utils.ListNode;
import com.zjw.algorithm.utils.Utils;

public class _删除链表的倒数第N个节点 {

    public static void main(String[] args) {
        System.out.println(Utils.toString(new _删除链表的倒数第N个节点().removeNthFromEnd(Utils.asNodeList(new int[]{1, 2}), 1)));
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }

        ListNode p1 = head;
        ListNode p2 = head;
        int count = 1;

        while (p1 != null) {
            p1 = p1.next;
            //找到倒数第n+1个节点
            if (count > n + 1) {
                p2 = p2.next;
            }
            count++;
        }

        if (count > n + 1) {
            ListNode deleteNode = p2.next;
            if (deleteNode.next == null) {
                p2.next = null;
            } else {
                p2.next = deleteNode.next;
                deleteNode.next = null;
            }
        } else {
            //删除p2自己
            ListNode newHead = p2.next;
            p2.next = null;
            return newHead;
        }
        return head;
    }
}
